To improve user experience, many modern navigation and/or other location-based systems (e.g., embedded systems such as in-vehicle navigation systems, as well as standalone systems such as personal navigation devices and/or mobile devices running navigation applications) provide for voice-based interactions. For example, a voice destination entry (VDE) system is able to configure the destination of the navigation system via a speech interface. However, implementing automatic speech recognition (ASR) for the speech interface can be a significant technical challenge particularly in embedded and portable systems where available resources (e.g., memory, processing power, network bandwidth, etc.) can be limited. For example, having a larger number of valid utterances to provide for more natural voice interaction also means dedicating more system memory to a larger speech decoding graph (e.g., a graph for converting utterances in a voice input signal into geographic information such as a navigation destination). Accordingly, service providers and device manufacturers face significant technical challenges to enabling efficient and natural speech interactions, particularly in resource-constrained devices.